/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */

// @lc code=start
class Solution 
{
public:
	vector<vector<string>> solveNQueens(int n) 
	{
		auto solutions = vector<vector<string>>();	//记录答案（记忆C++中变量定义的一种方法）
		auto queens = vector<int>(n, -1);			//queens[i]，代表Q应该被放置在第i行的第queens[i]个位置；	
		auto columns = unordered_set<int>();		//哈希集，记录已经放置了Q的列序号。
		auto diagonals1 = unordered_set<int>();		//哈希集，记录已经放置了Q的主对角线序号。(<左上 -> 右下>”，“行序号 - 列序号”为“固定值”。范围为[-(n-1), n-1]。)
		auto diagonals2 = unordered_set<int>();		//哈希集，记录已经放置了Q的副对角线序号。(<左下 -> 右上>”，“行序号 + 列序号”为“固定值”。范围为[0, 2n-2]。)
		backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
		return solutions;
	}

	/*函数功能	：用于生成满足返回格式的答案。
	返回值		：字符串数组（一个字符串代表一行，一个字符串数组就代表了一个二维格式的答案）
	形参		：	1、solutions：	二维字符串数组，每一行中的所有字符串组成1个答案。
					2、queens：		queens[i]，代表Q应该被放置在第i行的第queens[i]个位置；	
					3、n：			代表n皇后问题（即有几行）
					4、row：		代表从第row行开始处理（当row为n时，说明1中符合要求的情况已经生成）。
					5、columns：	哈希集，记录已经放置了Q的列序号。
					6、diagonals1：	哈希集，记录已经放置了Q的主对角线序号。(<左上 -> 右下>”，“行序号 - 列序号”为“固定值”。范围为[-(n-1), n-1]。)
					7、diagonals2：	哈希集，记录已经放置了Q的副对角线序号。(<左下 -> 右上>”，“行序号 + 列序号”为“固定值”。范围为[0, 2n-2]。)
	*/
	void backtrack(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) 
	{
		if (row == n)	//已经处理到第n行了，说明当前n皇后问题已经处理完，可以生成一个符合要求的情况。
		{
			vector<string> board = generateBoard(queens, n);	//生成1种符合要求的情况
			solutions.push_back(board);		//将符合要求的情况汇总到答案中
		}
		else 
		{
			for (int i = 0; i < n; i++)		//这里i代表：（1）列的序号<用于遍历>
			{
				/*确认i这个列序号还没有被Q占用。（当columns的集合中没有i时，往下执行；当columns中有i时，i++。）*/
				if (columns.find(i) != columns.end()) 
				{
					continue;
				}

				/*确认“row - i”这个主对角线序号还没有被Q占用。
				（row - columns = diagonal1;即diagonal1代表“主对角线方向<左上 -> 右下>”，“行序号 - 列序号”为“固定值”。范围为[-(n-1), n-1]。）*/
				int diagonal1 = row - i;	
				if (diagonals1.find(diagonal1) != diagonals1.end()) 
				{
					continue;
				}

				/*确认“row + i”这个副对角线序号还没有被Q占用。
				（row + columns = diagonal2;即diagonal2代表“副对角线方向<左下 -> 右上>”，“行序号 + 列序号”为“固定值”。范围为[0, 2n-2]。）*/
				int diagonal2 = row + i;
				if (diagonals2.find(diagonal2) != diagonals2.end()) 
				{
					continue;
				}

				queens[row] = i;	//就把Q放在第row行，第i列这个位置（这是基于上面3个条件判断的）
				columns.insert(i);				//在列的哈希集columns中标记列i的序号已经被占用
				diagonals1.insert(diagonal1);	//在主对角线的哈希集diagonals1中标记主对角线diagonals1的序号已经被占用
				diagonals2.insert(diagonal2);	//在副对角线的哈希集diagonals2中标记副对角线diagonals2的序号已经被占用
				backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);	//处理第row + 1行（已经处理完第row行了）

				//一下4个步骤就是回溯处理
				queens[row] = -1;
				columns.erase(i);
				diagonals1.erase(diagonal1);
				diagonals2.erase(diagonal2);
			}
		}
	}

	/*函数功能	：用于生成满足返回格式的答案。
	返回值		：字符串数组（一个字符串代表一行，一个字符串数组就代表了一个二维格式的答案）
	形参		：	1、queens：queens[i]，代表Q应该被放置在第i行的第queens[i]个位置；	
					2、n：代表n皇后问题（即有几行）
	*/
	vector<string> generateBoard(vector<int> &queens, int n) 
	{
		auto board = vector<string>();
		for (int i = 0; i < n; i++) 
		{
			string row = string(n, '.');
			row[queens[i]] = 'Q';
			board.push_back(row);
		}
		return board;
	}
};
// @lc code=end

